The present invention relates to a task scheduling method for controlling the priorities with which individual tasks are to be executed in a computer system incorporating a shared resource or resources such as I/O devices or files to be used in common by a plurality of tasks.
In a conventional task scheduling method, the task performs a processing for occupying the requisite shared resource (this processing is referred to as "lock processing") and a processing for releasing the shared resource from the occupied state (referred to as "unlock processing"), as is disclosed, for example, in Madnick, S. E. and Donovan, J. J. , "Operating System" published by McGraw Hill of New York in 1974, pp. 209-267. The task successfully occupying the shared resource or the task having no need to use the shared resource is referred to as the task in the execution-ready state or the execution-ready task or simply as the ready task. From a plurality of tasks, a task to be executed by an assigned CPU (central processing unit) or processor is appropriately selected by an operating system (dispatch program) provided separately for the purpose of task scheduling. Let's suppose that when a task (referred to as task 1 for convenience of discussion) is running in the state locking a given shared resource, and some sort of interrupt takes place. In that case, the task 1 is once changed to the execution-ready state from the running state, whereon an interrupt processing task (termed the task 2) provided separately is activated. Upon completion of the processing for the task 2, one of the plural tasks held in the execution-ready state is selected for execution by the above-mentioned dispatch program on the basis of priorities allocated previously to the individual tasks of the ready state, respectively. In this connection, problems will arise. More specifically, suppose that another task (termed the task 3) other than the above-mentioned task 1 starts to run after the interrupt processing and requires the use of the shared resource which is locked by the task 1. In this case, the task 3 can not use the shared resource locked by the task 1 and is placed in the queue waiting for the release of the shared resource until the locking task 1 has been executed and the shared resource is released from the locked state. Consequently, suppose a further ready-task 4 starts to run and encounters the same situation as the task 3 mentioned above. As a result, the processing steps involved in the unlock wait processing, the task discontinue (or suspend) processing as well as failure in acquiring the lock due to activation of other processing increases the total number of the steps to be executed.
To cope with the problem described above, there is known from JP-A-59-190950 a task priority control method in which when a conflict occurs among the tasks using the shared resource, as described above, the priority assigned to the task 1 locking the shared resource is made higher than the level which can be set by the user so that the task 1 can be executed with priority over the others. This in turn allows the use of the shared resource by the task 1 to be ended earlier.
Further, there is known a task priority scheduling method from JP-A-62-65137 according to which the higher one of the priorities assigned to the user task 1 locking the shared resource and the user task 2 awaiting the use of the shared resource, respectively is reassigned as priority to the user task 1 for allowing the latter to be executed with priority over the task 2.
According to the conventional systems disclosed in JP-A-59-170950 and JP-A-62-65137, the tasks are rescheduled with respect to the priorities by using the shared resource and taking advantage of the occurrence of conflicts when using the shared resource. Consequently, there may take place such undesirable situations that (1) re-execution of processing for the task 1 once discontinued due to the interrupt such as I/O interrupt is replaced by execution of the task 2 having the same priority level as that of the task 1 and (2) the task 2 is placed exclusively in the resource request queue when a plurality of tasks (tasks 1 and 2) are concurrently executed by a multiprocessor system.
In case (1) mentioned above, a processing (i) for placing the task 2 in the resource request queue is first performed, being then followed by a processing (ii) for placing the task 2 in the execution waiting state while placing the task 1 in the execution-ready state according to the conventional system. After the exclusive use of the shared resource by the task 1, a processing (iii) for imparting the right of exclusive use of the shared resource to the task 2 is performed. Subsequently, the shared resource is used exclusively by the task 2 (iv). This means for the succeeding task 3 that the period during which the shared resource is exclusively occupied by the task 2 increases from the time or period required for the processing (iv) to a sum of the periods required for the processings (i), (ii), (iii) and (iv), respectively.
Similarly, in the case (2) mentioned above, a processing (i) for placing the task (2) in the resource request queue is performed by another processor in parallel with the exclusive use of the shared resource by the task (1). Even when the exclusive use of the shared resource by the task (1) is ended, a processing (iii) for giving the right of exclusive use of the resource to the task (2) to set the latter in the execution waiting state must wait (v) till the end of the processing (i). Subsequently, the shared resource is then used exclusively by the task (2) . This means for the succeeding task (3) that the period for which the shared resource is occupied by the task 2 increases from the period (iv) to a sum of (v), (iii) and (iv).
Under these circumstances, the probability of the succeeding task (3) using the shared resource during the executive use thereof by the task (2) is increased. In general, since the total period for the processings (i), (ii) and (iii) or (v) and (iii) is far longer than the period (iv), the probability of use of the shared resource by the succeeding tasks increases rapidly, wherein these tasks are placed in the queue state from one to another, which in turn means that the overhead of the processings (i) and (ii) is increased thus lowering the throughtput.